package offer;

import sort.DuiSort;

import java.util.Arrays;
import java.util.PriorityQueue;

public class  Offer40 {
//    快速排序
    public  int[] quickSort(int[] nums){
        if (nums.length==0){
            return nums;
        }
        sort(nums,0,nums.length-1);
        return nums;
    }

    public  void sort(int[] nums,int lo,int hi){
        if (lo>=hi){
            return;
        }
        int partition = findPartition(nums, lo, hi);
        sort(nums, lo, partition-1);
        sort(nums,partition+1,hi);
    }

    public  int findPartition(int[] nums,int lo,int hi){
        int cur=nums[lo];
        int j=lo+1;
        int k=hi;

        while (j<k&&j<=hi&&k>=lo){
            while (j<=hi&&nums[j]<cur){
                j++;
            }
            while (k>=lo&&nums[k]>cur){
                k--;
            }
            if (j>=k){
                break;
            }
            swap(nums,j,k);
        }

//        todo:尝试 一下返回j行不行  尝试了一下 这个用j 来交换不行    现在想明白了 这个地方一定要是用k来交换
//         因为k停止循环的时候nums[k]<=cur 此时交换位置恰好将数组以lo处的元素为分界线 将数组一份为二 左边的数字小于lo处的元素  右边的数值大于lo处的元素
//        下面返回k也是同样的道理
        swap(nums,lo,k);
        return  k;
    }


    public  void swap(int[] nums,int j,int k){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }



    public  int[] mergeSort(int[] nums){
        if (nums.length==0){
            return nums;
        }
        int[] temp=new int[nums.length];
        sort(nums,0, nums.length-1,temp);
        return  nums;
    }

    public  void  sort( int[] nums,int lo,int hi,int[] temp){
        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }
    public  void merge(int[] nums,int lo,int mid,int hi,int [] temp){
        int j=lo;
        int k=mid+1;
        int i=0;
        while (j<=k&&j<=mid&&k<=hi){
            if (nums[j]<=nums[k]){
                temp[i++]=nums[j++];
            }else{
                temp[i++]=nums[k++];
            }
        }
        while (j<=mid){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }
        for (int l = 0; l <i ; l++) {
            nums[lo+l]=temp[l];
        }
    }



    public static void main(String[] args) {
        Offer40 offer40 = new Offer40();
        int[] nums={1,3,2,45,6};
        int[] ints = offer40.quickSort(nums);
        for (int a: ints
             ) {
            System.out.println(a);

        }
        Arrays.copyOfRange(ints,0,3);
    }



    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            if (k == 0 || arr.length == 0) {
                return new int[0];
            }
            // 最后一个参数表示我们要找的是下标为k-1的数
            return quickSearch(arr, 0, arr.length - 1, k - 1);
        }

        private int[] quickSearch(int[] nums, int lo, int hi, int k) {
            // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
            int j = partition(nums, lo, hi);
            if (j == k) {
                return Arrays.copyOf(nums, j + 1);
            }
            // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
            return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
        }

        // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
        private int partition(int[] nums, int lo, int hi) {
            int v = nums[lo];
            int i = lo, j = hi + 1;
            while (true) {
                while (++i <= hi && nums[i] < v);
                while (--j >= lo && nums[j] > v);
                if (i >= j) {
                    break;
                }
                int t = nums[j];
                nums[j] = nums[i];
                nums[i] = t;
            }
            nums[lo] = nums[j];
            nums[j] = v;
            return j;
        }
    }
}

class Solution {

    //TODO:2023/7/15 答案给出的方法
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while (true) {
            while (++i <= hi && nums[i] < v);
            while (--j >= lo && nums[j] > v);
            if (i >= j) {
                break;
            }
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }


    //TODO:2023/7/15 第二种方法
    public  int[] findKnum(int[] nums,int k){
        if (nums.length==0|k==0){
            return  new int[0];
        }

        PriorityQueue<Integer> queue = new PriorityQueue<>((v1,v2)->v2-v1);

        for (int a: nums) {

            if (queue.size()<k){
                queue.offer(a);
            }
            //TODO:2023/7/15 这一块逻辑不太对
//            else {
//                queue.poll();
//                queue.add(a);
//            }
            else  if (a< queue.peek()){
                queue.poll();
                queue.offer(a);
            }

        }
        int[]  res= new int[queue.size()];
        int i=0;
        while (!queue.isEmpty()){
            res[i++]= queue.poll();
        }
        return  res;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] knum = solution.findKnum(new int[]{1, 3, 2, 5}, 2);
        for (int a : knum
             ) {
            System.out.println(a);

        }
    }



}

